Motivated from the theory of non-parametric regression, we introduce a \emph{new variational constraint} that enforces the comparator sequence to belong to a discrete $k^{th}$ order Total Variation ball of radius $C_n$. This variational constraint models comparators that have piece-wise polynomial structure which has many relevant practical applications [Tibshirani2015]. By establishing connections to the theory of wavelet based non-parametric regression, we design a \emph{polynomial time} algorithm that achieves the nearly \emph{optimal dynamic regret} of $\tilde{O}(n^{\frac{1}{2k+3}}C_n^{\frac{2}{2k+3}})$. The proposed policy is \emph{adaptive to the unknown radius} $C_n$. Further, we show that the same policy is minimax optimal for several other non-parametric families of interest.

This paper considers the online trend estimation in the non-stationary stochastic optimization framework, where the comparator sequence satisfy certain variational constraints. The main contribution is a polynomial time policy extending Vovk-Azoury-Warmuth forecaster the achieves the minimax optimal rate for dynamic regret. All reviewers liked the paper, appreciating connecting the batch non-parametric regression to online stochastic optimization, techniques from wavelet computation, a model based on variational constraints which nicely captures sparsity and intensity of changes, and the (asymptotically) optimal algorithm.

Motivated from the theory of non-parametric regression, we introduce a \emph{new variational constraint} that enforces the comparator sequence to belong to a discrete k {th} order Total Variation ball of radius C_n . This variational constraint models comparators that have piece-wise polynomial structure which has many relevant practical applications [Tibshirani2015]. The proposed policy is \emph{adaptive to the unknown radius} C_n . Further, we show that the same policy is minimax optimal for several other non-parametric families of interest.